package problem003

// 用了分治的思想，根据题意可得
// 从数组中选取数字，和目标数字的关系有三种情况：=，<或>。
// 如果是等于则查找成功；
// 如果是数组中元素小于要查找的数字，说明要查找的数字应该在当前位置的右边或下边。
// 如果是数组中元素大于要查找的数字，说明要查找的数字应该在当前位置的左边或上边。
// 即 对于数组中的任何一个元素, 比它小的元素都在它的左方或者上方, 比它大的元素都在它的右边或者下方
// 但是这两个区域还有可能有重叠，比如右边或下边会在右下角有重叠。

// 为了不重复的处理重叠的数据, 我们可以找几个特殊的起点, 比如

// 起点	 	性质							可否作为起点
// 左上角		没有上方元素(小)和左方元素(小)
// 			只有下方元素(大)和右方元素(大)		否

// 右上角		没有上方元素(小), 和右方元素(大)
// 			只有下方元素(大)和左方元素(小)		是

// 左下角		没有下方元素(大), 和左方元素(小)
// 			只有上方元素(小)和右方元素(大)		是

// 右下角		没有下方元素(大), 和右方元素(大)
// 			只有上方元素(小)和左方元素(小)		否

// 因此重叠问题的解决方法：
// 如果查找从右上角开始，如果要查找的数字不在右上角，则每次可以剔除一列或一行。
// 也可以从左下角开始
// 但是不能从左上角或者右下角开始。


func Find(board [][]int, target int) bool {
	rlen := len(board)
	clen := len(board[0])

	//  我们从右上角的元素找起来
	for r,c:=0,clen-1; r<rlen && c>=0; {
		if board[r][c] == target {
			return true
		}
		if board[r][c] > target {
			c--
			continue
		} else {
			r++
		}
	}
	return false
}
